package 剑指offer;

import java.util.HashMap;
import java.util.Map;

public class _48最长不含重复字符的子字符串 {
	public static void main(String[] args) {
		
	}
	/**
	 * 
	 *@time 2021年3月20日上午9:21:16
	 * 
	 *@param s
	 *@return int
	 *
	 *@seehuakuai滑块思想
	 */
    public int lengthOfLongestSubstring(String s) {
    		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    		int leftIndex=-1,res=0;
    		
    		for (int i = 0; i < s.length(); i++) {
				if (map.containsKey(s.charAt(i))) {//当出现重复的字符时，将左边界移到map中出现重复的地方
					leftIndex = Math.max(leftIndex, map.get(s.charAt(i)));
				}
				map.put(s.charAt(i),i);
				res = Math.max(res, i-leftIndex);//i-leftIndex不包含左边界
			} 		    	   	
    		return res;
    }
    /**
     * 
     *@time 2021年3月20日上午9:35:54
     * 
     *@param s
     *@return int
     *
     *@see动态规划
     *动态转移方程为
     *
     *dp[j] = dp[j-1]+1 当dp[j-1]<j-i 说明：未出现重复的元素
     *dp[j] = j-i		当dp[j-1]>=j-i 说明：出现重复的元素
     *初始值：i=-1，j=0
     *最终的解为dp中最大的
     */
    public int lengthOfLongestSubstring1(String s) {
    	  Map<Character, Integer> map = new HashMap<>();
    	  int []dp  = new int[s.length()+1];
    	  dp[0] = 0;
    	  for (int j = 0; j < s.length(); j++) {
    		// getOrDefault方法，当中包含了key则返回value，否则返回后面的那个参数
    		  int i = map.getOrDefault(s.charAt(j), -1); 
    		  map.put(s.charAt(j),j);
    		  dp[j+1] = dp[j] >= j-i ? j-i : dp[j]+1;
    		  
		}
    	  int res =dp[0];
    	  for (int i = 0; i < dp.length; i++) {
			if (res<dp[i]) {
				res = dp[i];
			}
		}
    	  return res;
    }
}
